package twentytwentyone_2;

/**
 * @Author: Zahi
 * @Description:
 * @Date Created in 2021-02-22 17:05
 * @Modified By:
 */
public class IslandPerimeter_463 {

    public static void main(String []args){
        int[][] grid = new int[][]{{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}};
        System.out.println(islandPerimeter(grid));
    }

    /**
    *@Description 求岛屿周长
    *@Params [grid]
    *@Return int
    *@Author Zahi
    *@Date Created in 2021/2/23 13:02
    **/
    public static int islandPerimeter(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    // 题目限制只有一个岛屿，计算一个即可
                    return dfs(grid, i, j);
                }
            }
        }
        return 0;
    }

    /**
    *@Description dfs遍历岛屿，在边聊所有格子的过程中求出周长
    *@Params [grid, row, col]
    *@Return int
    *@Author Zahi
    *@Date Created in 2021/2/23 13:03
    **/
    public static int dfs(int [][] grid, int row, int col){

        // 如果下一步是边界，则周长加一
        if (!(row >= 0 && row < grid.length && col >= 0 && col < grid[0].length)){
            return 1;
        }

        // 如果下一步是水域，则周长加一
        if (grid[row][col] == 0){
            return 1;
        }

        //其余的为无效的区域，直接返回
        if (grid[row][col] != 1){
            return 0;
        }

        grid[row][col] = 2;

        // 向上走
        return dfs(grid,row - 1 ,col)+

        // 向左走
        dfs(grid,row,col - 1)+

        // 向下走
        dfs(grid,row + 1,col)+

        // 向右走
        dfs(grid,row,col + 1);
    }
}
